/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        106.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/15 16:47
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//根据一棵树的中序遍历与后序遍历构造二叉树。
//
//注意:
//你可以假设树中没有重复的元素。
#include "../header.h"

class Solution {
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        int n = inorder.size();
        for (int i = 0; i < n; ++i) {
            index[inorder[i]] = i;
        }
        return buildTree(inorder, postorder, 0, n - 1, 0, n - 1);
    }

private:
    unordered_map<int, int> index;

    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder,
                        int in_left, int in_right,
                        int post_left, int post_right) {
        if (post_left > post_right)
            return nullptr;
        int n = inorder.size();
        TreeNode *root = new TreeNode(postorder[post_right]);
        int in_root = index[postorder[post_right]];
        int left_num = in_root - in_left;
        root->left = buildTree(inorder, postorder,
                               in_left, in_root - 1, post_left, post_left + left_num - 1);
        root->right = buildTree(inorder, postorder,
                                in_root + 1, in_right, post_left + left_num, post_right - 1);
        return root;
    }
};
